"""
题目：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
    给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
    示例 1：
    输入：head = [1,2,3,4,5], n = 2
    输出：[1,2,3,5]
思路：采用双指针的方法来做，首先让第一个指针first向前走N步，第2个指针指向dummy，此时first和second之间相差n+1步，这样一来，当first走到链表的末尾（即None）时，seconde的下一个结点即为待删结点。
     核心思想是：first和second同时向后移动，当first指向链表的末尾时，second指向待删结点的前一个结点。
时间复杂度：O(L)
空间复杂度：O(1)
"""
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0,head)
        first = head
        second = dummy
        for i in range(n):
            first = first.next
        while first:
            first = first.next
            second = second.next
        second.next = second.next.next
        return dummy.next